package dp;

public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        // 题目要求的最终结果是dp(amount)
        return dp(coins, amount);
    }

    /**
     * 定义：要凑出目标金额amount，至少要dp(coins, amount)个金币
     * @param coins
     * @param amount
     * @return
     */
    private int dp(int[] coins, int amount) {
        // base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);
            // 子问题无解则跳过
            if (subProblem == -1) continue;;
            // 在子问题中选择最优解，然后 - 1
            res = Math.min(res, subProblem + 1);
        }

        return res == Integer.MAX_VALUE ? - 1 : res;
    }
}
